﻿package kizzo.datastruct 
{	

	public class BinaryHeap 
	{
		private var heap_array:Array;
		private var compare_func:Function;		
		private var _depth:uint;
		
		/*
		 * Creates a binary heap structure.
		 */
		public function BinaryHeap() 
		{
			this.heap_array = [];
			this.compare_func = less_than;
		}
		
		/*
		 * Add a node to the heap. The node will be placed in position depending on the selected compare function
		 */
		public function addNode(node:HeapNode):void
		{
			var node_index:int = this.heap_array.length;
			var parent_node_index:int = (node_index - 1) / 2;
			
			this.heap_array[node_index] = node;			
			
			while (node_index > 0)
			{
				if (!this.compare_func.apply(this, [this.heap_array[node_index].key, this.heap_array[parent_node_index].key]))
					break;
					
				this.swap_nodes(node_index, parent_node_index);
				//trace("swapping: " + node_index + " " + parent_node_index);
				node_index = parent_node_index;
				parent_node_index = (node_index - 1) / 2;
			}
		}
		
		/*
		 * Returns the HeapNode on top of the heap and replaces it.
		 */
		public function getNode():HeapNode
		{	
			swap_nodes(0, this.heap_array.length - 1);
			var return_node:HeapNode = this.heap_array.pop();
			
			var current_index:int = 0;
			var child_index_left:int = 1;
			var child_index_right:int = 2;
			var selected_child_index:int;
			
			while (1)
			{				
				selected_child_index = compare_get(child_index_left, child_index_right);
				
				if (selected_child_index > 0)
				{
					if (this.compare_func.apply(this, [this.heap_array[selected_child_index].key, this.heap_array[current_index].key ]))
					{
						swap_nodes(selected_child_index, current_index);
						current_index = selected_child_index;
						child_index_left = 2 * current_index + 1;
						child_index_right = 2 * current_index + 2;
					}
					else
						break;
				}
				else
					break;
			}
			
			return return_node;
		}
		
		
		private function compare_get(index1:int, index2:int):int
		{
			var index:int = -1;			
			
			if (index2 < this.heap_array.length)
			{
				if (this.compare_func.apply(this, [this.heap_array[index1].key, this.heap_array[index2].key]))
					index = index1;
				else
					index = index2;
			}
			else if (index1 < this.heap_array.length)
				index = index1;
				
			return index;
		}
		
		/*
		 * Traces the heap with text.
		 */
		public function traceHeap():void
		{	
			trace("\n\n\-------------------------------");
			for (var i:uint = 0; i < this.heap_array.length; i++)
			{				
				trace("I:" + i + " D:" + (Math.floor(Math.log(i + 1) / Math.log(2)) + 1)  + " K:" + heap_array[i].key);				
			}
		}
		
		/*
		 * The number of nodes a heap contains.
		 */
		public function get length():int
		{
			return this.heap_array.length;
		}
		
		
		private function swap_nodes(index1:int, index2:int):void
		{
			var buf:HeapNode = heap_array[index1];
			heap_array[index1] = heap_array[index2];
			heap_array[index2] = buf;
		}
		
		
		private static function less_than(num_1:int, num_2:int):Boolean
		{			
			if (num_1 < num_2)
				return true;
				
			return false;
		}

		private static function greater_than(num_1:int, num_2:int):Boolean
		{			
			if (num_1 > num_2)
				return true;
				
			return false;
		}		
		
	}
	
}